Motion estimation is a useful tool in various image-processing operations such as video compression and mosaic image generation. In video compression, motion estimation is used to minimize redundancy between successive video frames to render pictures of higher quality without increasing the data amount for each video frame. In mosaic image generation, motion estimation is used to map video frames to create mosaic images. A mosaic image is a composite image that is created by stitching together successively captured video frames.
For mosaic image generation, the desired characteristics of the motion estimation include real-time output and accuracy. Since mosaic image generation typically involves extremely high video data rates, real-time output of the motion estimation is desired to discard frames with no new useful information. In addition, the motion estimation should be accurate as possible so that new information from subsequent frames can be placed appropriately within the context of the acquired information from the previous frames to prevent misalignment of pixel intensities in the resulting mosaic image, which will degrade the quality of the mosaic image.
Conventional motion estimation techniques commonly utilize block matching to estimate motion between two successive video frames, a reference video frame and a target video frame. The target video frame is typically the later captured video frame with respect to the reference video frame. In a block-matching motion estimation technique, a number of candidate blocks of the target video image are selected for motion estimation. Each candidate block is then correlated with all the blocks within a search window of a reference image to determine the position of a block within the search window that best “match” that candidate block. The positions of these matched blocks of the reference video frame are then used to generate motion vectors that represent the displacements of the candidate blocks to estimate the motion between the target and the reference video frames.
A concern with the conventional motion estimation techniques is that the process of correlating the candidate blocks of a target video frame with the blocks of a reference image within the respective search windows is computationally intensive, and consequently, requires significant amount of processing time. As a result, a number of modifications have been proposed to decrease the computational requirement of the conventional motion estimation techniques, such as hierarchical block matching and heuristic search block matching. However, these modifications typically come at a cost with respect to the accuracy of the motion estimation.
In view of the above-described concern, there is a need for a system and method for estimating motion between video frames in a less computationally intensive manner without significantly reducing the accuracy of the motion estimation.